//package com.algo;
//
//public class RBTree<K extends Comparable<K>,V> {
//
//    private static final boolean RED = false;
//    private static final boolean BLACK = true;
//
//    private RBNode root;
//
//    public RBNode getRoot() {
//        return root;
//    }
//
//    public void setRoot(RBNode root) {
//        this.root = root;
//    }
//
//    /**
//     * 左旋
//     *      pf                   pf
//     *     /                    /
//     *    p                    pr
//     *   / \       ===>       / \
//     *  pl  pr               p  rr
//     *      / \             / \
//     *    rl   rr          pl rl
//     **/
//    private void leftRotate(RBNode p){
//        if(p!=null){
//            RBNode r = p.right;
//            p.right = r.left;
//            if(r.left!=null){
//                r.left.parent = p;
//            }
//            r.parent = p.parent;
//
//            if(p.parent==null){
//                root = r;
//            }else if(p.parent.left == p){
//                p.parent.left = r;
//            }else{
//                p.parent.right = r;
//            }
//
//            r.left = p;
//            p.parent = r;
//        }
//    }
//
//    /**
//     * 右旋
//     *            pf                      pf
//     *            /                      /
//     *           p(r)                   pl
//     *          / \     ====>           / \
//     *         pl  pr                  ll  p(r)
//     *        / \                         / \
//     *       ll rl                       rl  pr
//     **/
//    private void rightRotate(RBNode p){
//        if(p!=null){
//            RBNode l = p.left;
//            p.left = l.right;
//            if(l.right!=null){
//                l.right.parent = p;
//            }
//            l.parent = p.parent;
//
//            if(p.parent==null){
//                root = l;
//            }else if(p.parent.right == p){
//                p.parent.right = l;
//            }else{
//                p.parent.left = l;
//            }
//            l.right = p;
//            p.parent = l;
//        }
//    }
//
//    private RBNode parentOf(RBNode node){
//        return node==null?null:node.parent;
//    }
//
//    private RBNode leftOf(RBNode node){
//        return node!=null?node.left:null;
//    }
//    private RBNode rightOf(RBNode node){
//        return node!=null?node.right:null;
//    }
//
//    private boolean colorOf(RBNode node){
//        return node==null?BLACK:node.color;
//    }
//
//    private void setColor(RBNode node,boolean color){
//        if (node != null) {
//            node.color = color;
//        }
//    }
//
//    public void put(K key,V value){
//        RBNode t = this.root;
//        if(t==null){
//            //根节点
//            root = new RBNode<>(key, value == null ? key : value, null);
//            return;
//        }
//
//
//        RBNode parent;
//        if(key == null){
//            throw  new NullPointerException();
//        }
//        int cmp =0;
//        do {
//            parent = t;
//             cmp = key.compareTo((K) t.key);
//            if(cmp < 0){
//                t = t.left;
//            }else if(cmp > 0 ){
//                t = t.right;
//            }else{
//                t.setValue(value==null?key:value);
//                return;
//            }
//        }while (t !=null);
//
//        RBNode<K,Object> e = new RBNode<>(key,value==null?key:value,parent);
//        if(cmp < 0 ){
//            parent.left = e;
//        }else{
//            parent.right = e;
//        }
//
//        //调整
//        fixAfterPut(e);
//    }
//
//    private void fixAfterPut(RBNode x) {
//        x.color = RED;
//        //父节点是红色的时候才需要调整
//        while (x!=null&&x!=root&&x.parent.color==RED){
//            //x的父节点是爷爷的左节点
//            if (parentOf(x)==leftOf(parentOf(parentOf(x)))){
//                //拿到叔叔节点
//                RBNode y = rightOf(parentOf(parentOf(x)));
//                if(colorOf(y)==RED){
//                    setColor(parentOf(x),BLACK);
//                    setColor(y,BLACK);
//                    setColor(parentOf(parentOf(x)),RED);
//                    //爷爷节点递归
//                    x = parentOf(parentOf(x));
//                }
//                else{
//                    //左旋
//                    if (x == rightOf(parentOf(x))){
//                        x = parentOf(x);
//                        leftRotate(x);
//                    }
//                    setColor(parentOf(x),BLACK);
//                    setColor(parentOf(parentOf(x)),RED);
//
//                    //右旋
//                    rightOf(parentOf(parentOf(x)));
//
//                }
//            }else{
//                //拿到叔叔节点
//                RBNode y = leftOf(parentOf(parentOf(x)));
//                if(colorOf(y)==RED){
//                    setColor(parentOf(x),BLACK);
//                    setColor(y,BLACK);
//                    setColor(parentOf(parentOf(x)),RED);
//
//                    x = parentOf(parentOf(x));
//                }
//                else{
//                    if (x == leftOf(parentOf(x))){
//                        x = parentOf(x);
//                        rightRotate(x);
//                    }
//                    setColor(parentOf(x),BLACK);
//                    setColor(parentOf(parentOf(x)),RED);
//                    //右旋
//                    leftRotate(parentOf(parentOf(x)));
//
//                }
//            }
//        }
//        root.color = BLACK;
//    }
//
//    /**
//     * 小于节点的最大值
//     * @param node
//     * @return
//     */
//    private RBNode predecessor(RBNode node){
//        if(node ==null){
//            return null;
//        }
//        else if(node.left!=null){
//            RBNode p = node.left;
//            while(p.right!=null){
//                p = p.right;
//            }
//            return p;
//        }else{
//            RBNode p = node.parent;
//            RBNode child = node;
//            while(p!=null && child==p.left){
//                child = p;
//                p = p.parent;
//            }
//            return p;
//        }
//    }
//
//    /**
//     * 找后继节点，即大于节点的最小值
//     * @param node
//     * @return
//     */
//    private RBNode successor(RBNode node){
//        if(node==null){
//            return null;
//        }else if(node.right!=null){
//            RBNode p = node.right;
//            while(p.left!=null){
//                p = p.left;
//            }
//            return p;
//        }else{
//            RBNode p = node.parent;
//            RBNode child = node;
//            while(p!=null && child==p.right){
//                child = p;
//                p = p.parent;
//            }
//            return p;
//        }
//    }
//
//    static class RBNode<K extends Comparable<K>,V>{
//        private RBNode parent,left,right;
//        private boolean color;
//        private K key;
//        private V value;
//
//        public RBNode() {
//        }
//
//        public RBNode(K key, V value,RBNode parent) {
//            this.key = key;
//            this.value = value;
//            this.parent = parent;
//            this.color = BLACK;
//        }
//
//        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
//            this.parent = parent;
//            this.left = left;
//            this.right = right;
//            this.color = color;
//            this.key = key;
//            this.value = value;
//        }
//
//        public RBNode getParent() {
//            return parent;
//        }
//
//        public void setParent(RBNode parent) {
//            this.parent = parent;
//        }
//
//        public RBNode getLeft() {
//            return left;
//        }
//
//        public void setLeft(RBNode left) {
//            this.left = left;
//        }
//
//        public RBNode getRight() {
//            return right;
//        }
//
//        public void setRight(RBNode right) {
//            this.right = right;
//        }
//
//        public boolean isColor() {
//            return color;
//        }
//
//        public void setColor(boolean color) {
//            this.color = color;
//        }
//
//        public K getKey() {
//            return key;
//        }
//
//        public void setKey(K key) {
//            this.key = key;
//        }
//
//        public V getValue() {
//            return value;
//        }
//
//        public void setValue(V value) {
//            this.value = value;
//        }
//    }
//
//
//}
